package study.biggestsequence;

//Kadane's Algorithm 是一种用于在 O(n) 时间复杂度内找到最大子数组和的算法
public class KadaneAlgorithm {
    public static int[] maxSubArraySumWithRange(int[] nums) {
        if (nums == null || nums.length == 0) {
            return new int[]{0, -1, -1}; // 返回和、起始索引、结束索引，但这里表示空数组情况
        }

        int maxSoFar = nums[0];
        int maxEndingHere = nums[0];
        int start = 0, end = 0, tempStart = 0;

        for (int i = 1; i < nums.length; i++) {
            if (maxEndingHere + nums[i] > nums[i]) {
                maxEndingHere += nums[i];
            } else {
                maxEndingHere = nums[i];
                tempStart = i;
            }

            if (maxEndingHere > maxSoFar) {
                maxSoFar = maxEndingHere;
                start = tempStart;
                end = i;
            }
        }

        return new int[]{maxSoFar, start, end};
    }

    public static void main(String[] args) {
        int[] nums = {1, -12, 3, -5, 23, 3, -1, -12, 34, 5, -7,1,-5};
        int[] result = maxSubArraySumWithRange(nums);
        System.out.println("Maximum subarray sum is: " + result[0]);
        System.out.println("Start index is: " + result[1]);
        System.out.println("End index is: " + result[2]);
        // 输出应为：Maximum subarray sum is: 6, Start index is: 3, End index is: 6（对应子数组 [4, -1, 2, 1]）
    }
}
